using System;
using System.Collections.Generic;
using System.Text;


// for comparison reasons


namespace Mono.Boost.PriorityQueue
{
    /*
    public class IndexedBinaryHeapIntOLD : IPriorityQueue<int>
    {
        int[] heapKey;
        int[] heapVal;
        int[] hIndex;
        int size;
        public IndexedBinaryHeapIntOLD() { }
        public IndexedBinaryHeapIntOLD(int SizeOfHeap)
        {
            ((IPriorityQueue<int>)this).Create(SizeOfHeap);
        }

        void swap(int ind, int ind2) {
            int tmp = heapVal[ind2];
            heapVal[ind2] = heapVal[ind];
            heapVal[ind] = tmp;
            tmp = heapKey[ind2];
            heapKey[ind2] = heapKey[ind];
            heapKey[ind] = tmp;
            tmp = hIndex[tmp];
            hIndex[heapKey[ind]] = hIndex[heapKey[ind2]];
            hIndex[heapKey[ind2]] = tmp;
        }
        void HeapifyUp(int ind) {
            ind++;
            for(int ind2=ind/2;(ind>1)&&(heapVal[ind-1]<heapVal[ind2-1]);ind/=2,ind2/=2){             
                swap(ind-1,ind2-1);
            }
        }
        void HeapifyDown(int ind)
        {
            ind++;
            for (int ind2 = ind * 2; (ind2 <= size ) ; )
            {
                if (heapVal[ind - 1] > heapVal[ind2 - 1])
                {
                    swap(ind - 1, ind2 - 1);
                    ind *= 2;
                    ind2 *= 2;
                }
                else if ((ind2 != size ) && (heapVal[ind - 1] > heapVal[ind2]))
                {
                    swap(ind - 1, ind2);
                    ind = 2 * ind + 1;
                    ind2 = 2 * ind;
                }
                else break;
            }
        }
        int IPriorityQueue<int>.Size
        {
            get { return size; }
        }
        void IPriorityQueue<int>.Create(int SizeOfHeap)
        {
            heapKey = new int[SizeOfHeap];
            heapVal = new int[SizeOfHeap];
            hIndex = new int[SizeOfHeap];
            size = 0;
        }
        void IPriorityQueue<int>.Insert(int Key, int Value) 
        {
            heapVal[size] = Value;
            heapKey[size] = Key;
            hIndex[Key] = size;
            HeapifyUp(size);
            size++;
        }
        void IPriorityQueue<int>.DecreaseKey(int Key, int NewValue)
        {
            if (heapVal[hIndex[Key]] > NewValue)
            {
                heapVal[hIndex[Key]] = NewValue;
                HeapifyUp(hIndex[Key]);
            }
        }
        int IPriorityQueue<int>.TopKey
        {
        get 
        {
            return heapKey[0];
        }
        }
        int IPriorityQueue<int>.TopVal
        {
            get
            {
                return heapVal[0];
            }
        }
        void IPriorityQueue<int>.Pop() 
        {
            if (size > 0) {
                swap(0, size - 1);
                HeapifyDown(0);
            }
        }
    }



    public class IndexedBinaryHeapInt : IPriorityQueue<int>
    {
        int[] heap;
        int[] Val;
        int[] heapIndex;
        int size;
        public IndexedBinaryHeapInt() { }
        public IndexedBinaryHeapInt(int SizeOfHeap)
        {
            ((IPriorityQueue<int>)this).Create(SizeOfHeap);
        }

        void swap(int ind, int ind2) {
            int tmp = heap[ind2];
            heap[ind2] = heap[ind];
            heap[ind] = tmp;
            tmp = heapIndex[tmp];
            heapIndex[heap[ind]] = heapIndex[heap[ind2]];
            heapIndex[heap[ind2]] = tmp;
        }
        void HeapifyUp(int ind) {
            ind++;
            for(int ind2=ind/2;(ind>1)&&(Val[heap[ind-1]].CompareTo(Val[heap[ind2-1]])<0);ind/=2,ind2/=2){             
                swap(ind-1,ind2-1);
            }
        }
        void HeapifyDown(int ind)
        {
            ind++;
            for (; (ind*2 <= size ) ; )
            {
                if (Val[heap[ind*2 - 1]].CompareTo(Val[heap[ind - 1]])<0)
                {
                    swap(ind - 1, ind*2 - 1);
                    ind *= 2;
                }
                else if ((ind*2 != size ) && (Val[heap[ind*2]].CompareTo(Val[heap[ind-1]]))<0)
                {
                    swap(ind - 1, ind*2);
                    ind = 2 * ind + 1;
                }
                else break;
            }
        }

        int IPriorityQueue<int>.Size
        {
            get { return size; }
        }
        void IPriorityQueue<int>.Create(int SizeOfHeap)
        {
            heap = new int[SizeOfHeap];
            Val = new int[SizeOfHeap];
            heapIndex = new int[SizeOfHeap];
            size = 0;
        }
        void IPriorityQueue<int>.Insert(int Key, int Value) 
        {
            Val[Key] = Value;
            heap[size] = Key;
            heapIndex[Key] = size;
            HeapifyUp(size);
            size++;
        }
        void IPriorityQueue<int>.DecreaseKey(int Key, int NewValue){
            if (Val[Key] > NewValue)
            {
                Val[Key] = NewValue;
                HeapifyUp(heapIndex[Key]);
            }
        }
        int IPriorityQueue<int>.TopKey{
        get 
        {
            return heap[0];
        }
        }
        int IPriorityQueue<int>.TopVal
        {
            get
            {
                return Val[heap[0]];
            }
        }
        void IPriorityQueue<int>.Pop() 
        {
            if (size > 0) {
                swap(0, size - 1);
                HeapifyDown(0);
            }
        }
    }
    */
}